package com.leet.code;

import java.util.*;

public class Code347 {

    public static void main(String[] args) {
//        Map<Integer, Integer> map = new HashMap<>();
//        map.merge(1, 2, Integer::sum);

        int[] nums = {1, 1, 1, 2, 2, 3};

        System.out.println(Arrays.toString(new Code347().topKFrequent(nums, 2)));
    }

    public int[] topKFrequent(int[] nums, int k) {
        PriorityQueue<Map.Entry<Integer, Integer>> priorityQueue = new PriorityQueue<>(k, Comparator.comparingInt(Map.Entry::getValue));
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums) {
            Integer j = map.get(i);
            if (j == null) {
                j = 1;
            } else {
                j++;
            }
            map.put(i, j);
        }

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (priorityQueue.size() < k) {
                priorityQueue.add(entry);
            } else {
                if (priorityQueue.peek().getValue() < entry.getValue()) {
                    priorityQueue.poll();
                    priorityQueue.add(entry);
                }
            }
        }

        int i = 0;
        int[] ks = new int[k];
        Map.Entry<Integer, Integer>[] m = new Map.Entry[k];
        m = priorityQueue.toArray(m);

        while (i < k) {
            ks[i] = m[i].getKey();
            i++;
        }
        return ks;
    }
}
